package com.tyning.leetcode.jz59II;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

public class MaxQueue {
    Queue<Integer> queue = new LinkedList();
    Deque<Integer> deque = new LinkedList();

    public MaxQueue() {

    }

    public int max_value() {
        if (deque.isEmpty()) {
            return -1;
        }
        return deque.peekFirst();
    }

    public void push_back(int value) {
        // 一个新队列是先进入后出的，
        // 看队列的变化是否能够记录最大值：
        // 加入元素，可以在每次加入的时候和自己记录的最大值作比较
        // 如果推出元素的时候，如果出去的元素是我记录的最大值的话那么我这个最大值在新的队列中就是失效的，只要处理这一种情况那么这个思路就是通的
        // 如何处理出元素的时候形成新的队列的最大值是什么呢？
        // 我可以重新遍历一遍队列查找最大值这是一种方法
        // 不过队列有个特点出队列的时候永远是开头，加入的时候永远的队尾，那么在加入元素的时候或者说出元素的时候这个最大值是否有什么联系？
        // 因为有先后，加入一个元素的时候然后再加入一个元素的时候，如果后一个元素比前一个元素大的话，那么最大值一定是后边的元素，及时前一个元素出队列形成的
        // 新的队列的最大值也是后边的元素，这是加入的过程。如果是出元素的过程的话，不同的出元素，直到发现出的元素就是最大值的话，那么这个最大值就对新的队列不起作用了
        // 那么这个新队列的最大值一定是在这个队列后边，那么回头看这个新的队列的最大值，就是找这个队列的后边元素的最大值。其实也就是说，我得找从前到后找最大的值，然后再找
        // 比这个值最大值，然后从这个最大值往后比这个最大值第二大的值，这个怎么找，不要找，用形成也就是在加入一个元素的先认为是第二大的值。
        // 然后，后边再加入如果不是就移除，然后排到这个最大值后边，依次类推。

        while (!deque.isEmpty() && deque.peekLast() != null && deque.peekLast().intValue() < value){
            deque.pollLast();
        }
        deque.offerLast(value);
        queue.offer(value);
    }

    public int pop_front() {
        if (queue.isEmpty()) {
            return -1;
        }
        Integer pollvalue = queue.poll();
        Integer peekFirst = deque.peekFirst();
        if (peekFirst.intValue() == pollvalue.intValue()){
            deque.pollFirst();
        }
        return pollvalue;
    }
}
